문제
0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다.
- x에 있는 “110”을 뽑아서, 임의의 위치에 다시 삽입합니다.
예를 들어, x = “11100” 일 때, 여기서 중앙에 있는 “110”을 뽑으면 x = “10” 이 됩니다. 뽑았던 “110”을 x의 맨 앞에 다시 삽입하면 x = “11010” 이 됩니다.
변형시킬 문자열 x가 여러 개 들어있는 문자열 배열 s가 주어졌을 때, 각 문자열에 대해서 위의 행동으로 변형해서 만들 수 있는 문자열 중 사전 순으로 가장 앞에 오는 문자열을 배열에 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤ s의 길이 ≤ 1,000,000
- 1 ≤ s의 각 원소 길이 ≤ 1,000,000
- 1 ≤ s의 모든 원소의 길이의 합 ≤ 1,000,000
입출력 예
| s | result |
|---|---|
| [“1110”,”100111100”,”0111111010”] | [“1101”,”100110110”,”0110110111”] |
접근
우선 110을 어디에 넣어야 하는지를 정리해 보았습니다. 110 자체가 1과 0이 모두 포함되어 있으니 다음과 같습니다.
- 가장 뒤에 나오는 0 뒤
- 0이 없다면 가장 앞에 있는 1 앞
우선 문자열에서 “110”을 모두 제거한 후에, 삭제한 “110” 수 만큼 남은 문자열에 위 규칙대로 추가하면 가장 작은 문자열을 만들 수 있습니다.
여기서 포인트는 순차적으로 "110"을 삭제하면서, 다시 생기는 "110"을 또 삭제해줘야 하는 것입니다.
예를들어 11100에서 110을 삭제하면 110이 다시 남게됩니다. 이것도 삭제해 주어야 합니다.
- char array를 생성합니다. - list
- 원본 문자열의 문자를 하나씩 list에 삽입하면서 문자가 0일 경우…
- 110이 완성되었으면 list에서 110을 삭제합니다.
- 110을 삽입할 위치이니 index를 기록합니다.
- 다시 새로운 char array를 생성해 list의 0 ~ index까지 복사해 옵니다. 그 후에 110을 뒤에 추가합니다. list의 index+1 ~ 까지 복사합니다.
쉽게 두 가지 예시로 가져왔습니다.
예시 1: 11101
예시 2: 101100
Solution
관련 메소드 코드 가져왔습니다.
끝
시간 초과 고친다고 엄청 고생한 문젠데 같이 대회 참여하신 분들 정말 대단합니다…
배열 대신 ArrayList를 썼을 때는 4번 테케에서 시간초과 걸렸습니다.
그래도 이렇게나마 풀어서 뿌듯합니다.
감사합니다.
Text by Chaelin. Photographs by Chaelin, Unsplash.